#include <iostream>
#include <vector>
using namespace std;

const int SIZE = 9;
int matrix[SIZE][SIZE] = {
    {6, 5, 0, 8, 7, 3, 0, 9, 0},
    {0, 0, 3, 2, 5, 0, 0, 0, 8},
    {9, 8, 0, 1, 0, 4, 3, 5, 7},
    {1, 0, 5, 0, 0, 0, 0, 0, 0},
    {4, 0, 0, 0, 0, 0, 0, 0, 2},
    {0, 0, 0, 0, 0, 0, 5, 0, 3},
    {5, 7, 8, 3, 0, 1, 0, 2, 6},
    {2, 0, 0, 0, 4, 8, 9, 0, 0},
    {0, 9, 0, 6, 2, 5, 0, 8, 1}
};

// 输出结果
void printSudoku() {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            cout << matrix[i][j] << "\t";
        }
        cout << endl;
    }
}

// 返回下一个未填的格子
vector<int> numberUnassigned(int row, int col) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (matrix[i][j] == 0) {
                return {1, i, j};
            }
        }
    }
    return {0, -1, -1};
}

// 检查是否能将值n填写在单元格[r][c]处
bool isSafe(int n, int r, int c) {
    // 检查所在行有无重复
    for (int i = 0; i < SIZE; i++) {
        if (matrix[r][i] == n) return false;
    }
    // 检查所在列有无重复
    for (int i = 0; i < SIZE; i++) {
        if (matrix[i][c] == n) return false;
    }
    // 检查所在九宫格
    int row_start = (r / 3) * 3;
    int col_start = (c / 3) * 3;
    for (int i = row_start; i < row_start + 3; i++) {
        for (int j = col_start; j < col_start + 3; j++) {
            if (matrix[i][j] == n) return false;
        }
    }
    return true;
}

// 使用回溯法解决数独问题
bool solveSudoku() {
    int row = 0, col = 0;
    vector<int> a = numberUnassigned(row, col);
    if (a[0] == 0) return true;

    row = a[1];
    col = a[2];
    for (int i = 1; i <= SIZE; i++) {
        if (isSafe(i, row, col)) {
            matrix[row][col] = i;
            if (solveSudoku()) return true;
            matrix[row][col] = 0;
        }
    }
    return false;
}

int main() {
    if (solveSudoku()) {
        printSudoku();
    } else {
        cout << "该数独问题无解!" << endl;
    }
    return 0;
}